package pri.hillchen.algorithm.array;

import java.util.*;

/**
 * 小明陪小红去看钻石，他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。
 * 在他们们比较了一段时间后，它们看中了两颗钻石g1和g2。现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。
 * 给定两颗钻石的编号g1,g2，编号从1开始，同时给定关系数组vector,其中元素为一些二元组，第一个元素为一次比较中较重的钻石的编号，
 * 第二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系，若g1更重返回1，g2更重返回-1，无法判断返回0。
 * 输入数据保证合法，不会有矛盾情况出现。
 * 测试样例：
 * 2,3,[[1,2],[2,4],[1,3],[4,3]],4
 * 返回: 1
 * Created by hillchen on 2017/9/25 0025.
 */
public class SelectHeaviest {
    public int cmp(int g1, int g2, int[][] records, int n) {
        Map<Integer,Vector> directedGraph = createDirectedGraph(records,n);
        if(hasPathTo(g1,g2,directedGraph)){
            return 1;
        }else if(hasPathTo(g2,g1,directedGraph)){
            return -1;
        }else{
            return 0;
        }
    }

    /**
     * 根据有向图边集合信息创建单向有向图
     * 有向图用Map<Integer,Set<Integer>>来表示，key值为有向图边的起始顶点，value为有Set<Integer>为该顶点的所有出度顶点
     * 每条边的方向表示为起始顶点大于终止顶点
     * @return
     */
    private  Map<Integer,Vector> createDirectedGraph(int[][] records,int length){
        Map<Integer,Vector> retMap = new HashMap<Integer, Vector>();

        for(int i=0;i<length;i++){
            int[] record = records[i];
            Integer heavierNo = record[0];
            Integer lighterNo = record[1];
            if(!heavierNo .equals(lighterNo) ){
                Vector vector;
                if(retMap.containsKey(heavierNo)){
                    vector = retMap.get(heavierNo);
                }else{
                    vector = new Vector(heavierNo);
                    retMap.put(heavierNo,vector);
                }
                vector.addNextPoint(lighterNo);
            }
        }
        return retMap;
    }

    /**
     * 判断在单向有向图中是否存在从起始顶点到终止顶点的路径，因每条边的起始顶点大于终止顶点，
     * 则如果存在startNo到endNo的路径则可以断定startNo所对应的值大于endNo所对应的值
     * @param startNo
     * @param endNo
     * @param directedGraph
     * @return
     */
    private  boolean hasPathTo(int startNo,int endNo,Map<Integer,Vector> directedGraph){
        Queue<Vector> needVisitQueue = new LinkedList<Vector>();

        if(directedGraph.containsKey(startNo)){

            Vector rootVector = directedGraph.get(startNo);
            needVisitQueue.offer(rootVector);
            while (!needVisitQueue.isEmpty()){
                Vector currentVector =   needVisitQueue.poll();
                if(!currentVector.isVisited()){
                    currentVector.isVisited();
                    Set<Integer> nextPoints = currentVector.nextPoints;
                    if(nextPoints.contains(endNo) ){
                        return true;
                    }else{
                        for(Integer nextNo: nextPoints){
                            if(directedGraph.containsKey(nextNo)){
                                needVisitQueue.offer(directedGraph.get(nextNo));
                            }
                        }
                    }
                }
            }
        }
        return false;
    }

    class Vector{
        private Integer pointNo;
        private Set<Integer> nextPoints = new HashSet<Integer>();
        private boolean visited;

        public Vector(Integer pointNo) {
            this.pointNo = pointNo;
        }

        public boolean isVisited() {
            return visited;
        }

        public void setVisited(boolean visited) {
            this.visited = visited;
        }

        public void addNextPoint(Integer pointNo){
            this.nextPoints.add(pointNo);
        }
    }

    public static void main(String[] args){
        int[][] recodes = new int[][]{{5,5},{2,4},{8,6},{12,10},{12,12},{6,12},{2,3},{8,5},{7,5},{5,5},{3,10},{11,11},{12,12},{10,11},{7,3},{2,3},{11,5},{1,9},{8,12},{3,10},{8,4},{7,1},{9,5},{6,4},{1,11},{7,9},{12,12},{4,11},{8,6},{2,3},{12,5},{2,7},{4,11},{4,11},{3,3},{4,11},{3,4},{8,1},{10,9},{4,5},{6,9},{8,10},{7,11},{12,5},{2,12},{1,9},{7,3},{8,10},{2,1},{8,4},{3,11},{6,4},{2,4},{7,1},{6,6},{8,1},{1,4},{3,5},{12,10},{1,5},{2,4},{6,3},{7,12},{6,10},{6,11},{7,12},{7,4},{9,5},{2,11},{2,6},{6,5},{8,5},{1,9},{6,4},{7,1},{1,1},{2,9},{8,4},{6,5},{1,10},{6,3},{8,7},{8,2},{6,5},{2,12},{4,9},{7,11},{4,9},{2,10},{8,10},{12,10},{6,3},{2,10},{12,9},{8,4},{2,12},{7,11},{9,5},{3,5},{2,5},{7,9},{8,10},{7,9},{4,4},{2,3},{2,2},{7,3},{6,5},{2,4},{4,9},{8,10},{12,9},{2,9},{8,9},{12,5},{8,2},{3,12},{1,12},{1,12},{8,2},{2,5},{1,10},{12,5},{3,4},{8,11},{2,12},{8,2},{10,11},{8,3},{2,7},{8,6},{1,10},{7,12},{8,6},{1,1},{3,4}};
        System.out.println(new SelectHeaviest().cmp(12,2,recodes,136));
    }
}
